package 力扣算法练习.main1.part1;

import java.util.HashSet;
import java.util.Set;

public class day1 {
    /*
        给定一个整数数组 nums和一个整数目标值 target，请你在该数组中找出
        和为目标值 target 的那两个整数，并返回它们的数组下标。
        你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
        你可以按任意顺序返回答案。
        https://leetcode.cn/problems/two-sum
     */
    public int[] twoSum(int[] nums, int target) {
        //写一个双层for循环满足i位置加j位置的元素等于target就return
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return result;
    }

    /*
    给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
    https://leetcode.cn/problems/longest-substring-without-repeating-characters/
     */
/*    public static int lengthOfLongestSubstring(String s) {
        //将字符串的所有元素遍历同时将其存入set集合并且记数遇到的相同的就把set清空将计数归零
        if (s.isEmpty())return 0;
        if (s.trim().isEmpty())return 1;
        int result=0,max=0;
        Set<Character> temp=new HashSet<>();
        char tempChar;
        for (int i = 0; i < s.length(); i++) {
            tempChar=s.charAt(i);
            if (temp.isEmpty()){
                temp.add(tempChar);
                max++;
            }else{
                if (temp.contains(tempChar)){
                    if (max>result)result=max;
                    temp=new HashSet<>();
                    max=0;
                    temp.add(tempChar);
                    max++;
                }else{
                    temp.add(tempChar);
                    max++;
                }
            }
            if (max>result)result=max;
        }
        return result;
    }*/

    //官方解
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }

}
